package gold.digger;

import gold.vo.TreeNode;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC654 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTreeRecur(nums, 0, nums.length - 1);
    }

    public TreeNode constructMaximumBinaryTreeRecur(int[] arr, int start, int end) {
        if (null == arr || start > end) {
            return null;
        }

        if (start == end) {
            return new TreeNode(arr[start]);
        }

        int maxPos = start;
        for (int i = start; i <= end; i++) {
            if (arr[i] > arr[maxPos]) {
                maxPos = i;
            }
        }
        TreeNode head = new TreeNode(arr[maxPos]);
        head.left = constructMaximumBinaryTreeRecur(arr, start, maxPos - 1);
        head.right = constructMaximumBinaryTreeRecur(arr, maxPos + 1, end);
        return head;
    }

    public static void main(String[] args) {
        LC654 an = new LC654();
        int[] arr = {3, 2, 1, 6, 0, 5};
        System.out.println(an.constructMaximumBinaryTree(arr));

    }
}
